//给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != 
//k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 
//
// 你返回所有和为 0 且不重复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,1]
//输出：[]
//解释：唯一可能的三元组和不为 0 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [0,0,0]
//输出：[[0,0,0]]
//解释：唯一可能的三元组和为 0 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 3000 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// Related Topics 数组 双指针 排序 👍 6604 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-12-18 00:42:22
 * @description 15.三数之和
 */
public class ThreeSum{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ThreeSum().new Solution();
		solution.threeSum(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

		 //没法确定每次找到解之后，怎么缩小边界，会漏解
	public List<List<Integer>> threeSum1(int[] nums) {
		//结果
		List<List<Integer>> res = new ArrayList<>();
		//先排序
		Arrays.sort(nums);
		int l = 0, r = nums.length - 1, t;

		while (l + 1 < r&&nums[l]<=0 ) {
				int sum=nums[l]+nums[r];
			//如果最大的数相加正的太多 -2 + 8  6
			if (sum> 0 && sum+nums[l]>0) {
				r--;
				//如果最大的数相加都负的多，-8 + 2 -6
			} else if ((sum) < 0 && sum+nums[r]<0) {
				l++;
			} else {
				t=-sum;
				for (int i = l + 1; i < r; i++) {
					if (t == nums[i]) {
						res.add(new ArrayList<Integer>(Arrays.asList(nums[l], nums[r], t)));
						break;
					}
				}
				//sum小于0，缩小左边
				if (t > 0) {
					//去重
					while (l < r && nums[l] == nums[l + 1]) {
						l++;
					}
					l++;
					//sum>=0，缩小右边
				} else {
					while (l < r && nums[r] == nums[r - 1]) {
						r--;
					}
					r--;
				}
			}
		}
		return res;
	}
	public List<List<Integer>> threeSum(int[] nums){
		List<List<Integer>> res=new ArrayList<>();
		
		int length = nums.length;
		if(nums==null||length<3) return res;
		Arrays.sort(nums);

		for (int i = 0; i < length; i++) {
			//如果起始值已经大于0。中间找不到和小于0 的数
			if(nums[i]>0){
				break;
			}
			//去重，重复的元素只找第一个
			if(i>0&&nums[i]==nums[i-1]) continue;
			int l=i+1;
			int r=length-1;
			//找出与i相加等于0的所有lr
			while (l<r){
				int sum=nums[i]+nums[l]+nums[r];
					//等于0保存解
				if(sum==0){
					res.add(Arrays.asList(nums[i],nums[l],nums[r]));
					//去重，移动左右指针
					while (l<r&&nums[l]==nums[l+1]){
						l++;
					}
					while (l<r&&nums[r]==nums[r-1]){
						r--;
					}
					l++;
					r--;

				}else if(sum<0){
					l++;
				}else if(sum>0){
					r--;
				}
			}
		}
		return res;
		
	}
	 }
//leetcode submit region end(Prohibit modification and deletion)

}
